package leetcode.Hot100;

import leetcode.TreeNode;
import leetcode.TreeNodeUtil;

import java.util.Deque;
import java.util.LinkedList;

/**
 * @author Cheng Jun
 * Description: 给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
 * https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-tree/
 * @version 1.0
 * @date 2021/12/12 22:27
 * 二刷 面试题
 */
public class lowestCommonAncestor1 {
    static boolean flag = false;

    public static void main(String[] args) {
        TreeNode root = TreeNodeUtil.getBT(new Object[]{3, 5, 1, 6, 2, 0, 8, null, null, 7, 4});
        TreeNode p = new TreeNode(5);
        TreeNode q = new TreeNode(4);
        TreeNode treeNode = lowestCommonAncestor(root, p, q);
        System.out.println(treeNode.val);
    }

    // 找到 p 的所有祖先节点 pList， q 的所有祖先节点 qList，找到 pList 和 qList 最后一个相同的元素即为所求
    static TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        Deque<TreeNode> pList = new LinkedList<>();
        Deque<TreeNode> qList = new LinkedList<>();

        findAncestor(root, p, pList);
        flag = false;
        findAncestor(root, q, qList);

        TreeNode commonAncestor = root;
        while (!pList.isEmpty() && !qList.isEmpty()) {
            TreeNode head1 = pList.pop();
            TreeNode head2 = qList.pop();
            if (head1 == head2) {
                commonAncestor = head1;
            } else {
                break;
            }
        }
        return commonAncestor;
    }

    // 找到 node 的所有祖先节点
    static private void findAncestor(TreeNode root, TreeNode node, Deque<TreeNode> ancestorList) {
        //    1
        //  2   3
        //4   5    6
        if (root != null && !flag) {
            ancestorList.add(root);
            if (root.val != node.val) {
                findAncestor(root.left, node, ancestorList);
                findAncestor(root.right, node, ancestorList);
                if (!flag) {
                    ancestorList.remove(root);
                }
            } else {
                flag = true;
                return;
            }
        }
    }

    // 递归实现
    // https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-tree/solution/236-er-cha-shu-de-zui-jin-gong-gong-zu-xian-hou-xu/
    static TreeNode lowestCommonAncestor1(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null) return null;
        if (p.val == root.val || q.val == root.val) return root;
        TreeNode leftNode = lowestCommonAncestor1(root.left, p, q);
        TreeNode rightNode = lowestCommonAncestor1(root.right, p, q);
        if (leftNode != null && rightNode != null) return root;
        if (leftNode == null) return rightNode;
        if (rightNode == null) return leftNode;
        return null;
    }
}
